20240620 2748 - Easy - Array

2748. Number of Beautiful Pairs

Non-Brute Force Solution

• Use a cnt array to count the first number of number[i] from 0 to 10

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        ans = 0
        cnt = [0] * 10
        for x in nums:
            for y, c in enumerate(cnt):
                if c and gcd(y, x % 10) == 1:
                    ans += c
            while x >= 10: 
                x //= 10
            cnt[x] += 1  # 统计最高位的出现次数
        return ans